1. Technical Field
The present description relates to techniques for processing digital data.
One or more embodiments may apply to communication systems involving decoding of, e.g., convolutional codes.
One or more embodiments may apply to decoding convolutional codes and, as a consequence, turbo codes.
2. Description of the Related Art
In the design of digital systems, a fixed point representation may be adopted and one of the issues for the digital designer may be dimensioning, e.g., selecting the number of bits which may represent a particular quantity appearing in a procedure considered. This choice may be significant, as implementation complexity, dissipated energy and processing delay tend to grow with the number of bits, while the quality of the generated results may be degraded by a low number of allocated bits. In certain procedures, e.g., those organized in an iterative way, the dynamics of some quantities may evolve through the execution of the procedure: in these cases, dimensioning may be more difficult.
In certain cases, these quantities may be used for discrimination purposes, e.g., the values they assume may be compared with the values of other quantities or by a constant.
An order relationship may thus be present, and these quantities may be referred to as “metrics”.
The management of metrics may be important, e.g., in digital communication systems. There, channel encoding may be adopted at the transmitter side to protect the information transmitted from effects of the transmission channel. Repetition codes, block codes, convolutional codes, turbo codes and LDPC codes are exemplary of channel coding schemes. At the receiver side, channel decoding procedures may reconstruct the transmitted information.
Channel decoding procedures may use internal metrics to provide reliability information as regards the information transmitted, an objective being to discriminate the one message actually transmitted out of all the messages which may be transmitted.
The growth of internal metrics in channel decoding procedures is a known issue. In the case of channel codes relying on convolutional codes the problem may be faced with different approaches.
For instance, certain hardware-based decoding architectures may rely on fixed point implementation so the number of bits available for representing data may be limited.
Also, it was observed that the dynamic range of path metrics in, e.g., a Viterbi decoder may often tend to grow due to the fact that these metrics are iteratively obtained through sum operations. However, the difference among metrics, e.g., their distance, remains bounded in a range [−D/2, D/2].
This property may be exploited as disclosed, e.g., in A. P. Hekstra, “An alternative to metric rescaling in Viterbi decoders,” IEEE Transactions on Communications, vol. 37, no. 11, pp. 1220-1222, November 1989. There, wrapping of metrics (specifically the path metrics) for Viterbi decoding of convolutional codes is proposed: the underlying idea is to avoid metric normalization by limiting the metric representation to the range [−D/2, D/2−1] and looking at this range as circular.
This approach is based on the recognition that the Viterbi Algorithm (VA) has the property that its behavior is unaffected if a modulo operator is properly applied to the metrics; the modulo operation corresponds to the wrapping mechanism in two's complement arithmetic when an overflow occurs. From the arithmetic point of view, wrapping thus means that, when adding two or more data, overflow can occur, but it does not require to be handled.
For instance, for a generic metric β, [β]D=β ε for [−D/2, D/2−1], [β]D=β-D for β>D/2−1 and [β]D=β+D for β<−D/2 where the operator [·]D denotes the wrapping operation. When working with a fixed point 2's complement implementation, where D is a power of two, wrapping is automatic. In such an arrangement, metrics may only evolve circularly: if, for instance, D=32, this means that while, e.g., 1+3=4 and 7+12=19 without wrapping, with wrapping on still it is 1+3=4, but 7+12=−13.
In the following text, some numerical examples are given for the case D=32, that is for metrics represented by 5 (five) bits, by focusing on the order relationship ≧. Two metrics, e.g., β1 and β2 are exemplified, with |β1−β2|<D/2. In the following, the subscript “wrap” is used to distinguish the case where wrapping is allowed from the case where wrapping is avoided.
Case 1
(one family of metrics): no metric has wrappedβ1=15→β1,wrap=15β2=2→β2,wrap=2β1>β2 and β1,wrap>β2,wrap 
Case 2
(one family of metrics): two metrics have wrappedβ1=19→β1,wrap=−13β2=16→β2,wrap=−16β1>β2 and β1,wrap>β2,wrap 
Case 3
(one family of metrics): one metric has wrappedβ1=19→β1,wrap=−13β2=10→β2,wrap=10
β1β2 and apparently β1,wrap<β2,wrap. However, β1,wrap and β2,wrap are modulo D quantities so[β1,wrap−β2,wrap]D=[−13−10]32=[−23]32=9>0.
Hence β1,wrap>β2,wrap.
Wrapping thus preserves both distances and the order relationship ≧, and may be used to avoid normalization during the generation of metrics, e.g., in Viterbi decoding of a convolutional code.
In the case of Viterbi decoding just considered, only one family of metrics evolves (βj, j ε J where J is a finite set of indices).
In the case of certain procedures, plural families of metrics may be considered. For instance, in the case of Bahl, Cocke, Jelinek and Raviv (BCJR) decoding (as presented, e.g., in L. R. Bahl, J. Cocke, F. Jelinek, and J. Raviv, “Optimal decoding of linear codes for minimizing symbol error rate,” IEEE Transactions on Information Theory, vol. 20, no. 3, pp. 284-287, March 1974), a higher number of metrics may be dealt with, in comparison to Viterbi decoding: present or branch metrics, past or forward metrics, future or backward metrics, a posteriori metrics and extrinsic metrics.
These metrics combine with each other and the wrapping technique proposed, e.g., in Hekstra (previously cited) may not be directly applied to the whole decoding process. Indeed, the wrapping technique may be applied to the computation of past (α) and future (β) metrics, but, in order to combine them while preserving the order relationship, metric normalization may be required, thus adding implementation cost.
It may be noted that normalization has been considered unavoidable at some point of the chain, namely when past and future metrics have to be added together, and the sum of wrapped quantities destroys indeed the order relationships present in the α and β sets, respectively.